import { LinkList } from "./01_单向链表_重构";

class Node<T> {
  value: T;
  next: Node<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}

export class DoublyNode<T> extends Node<T> {
  prev: DoublyNode<T> | null = null;
  next: DoublyNode<T> | null = null;
}

export class DoublyLinkedList<T> extends LinkList<T> {
  protected head: DoublyNode<T> | null = null;
  protected tail: DoublyNode<T> | null = null;

  //在链表尾部加入节点
  append(value: T): void {
    const newNode = new DoublyNode(value);

    if (!this.head) {
      //空白链表第一次添加节点
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.size++;
  }

  //在链表头部加入节点
  prepend(value: T): void {
    const newNode = new DoublyNode(value);

    if (!this.head) {
      //空白链表第一次添加节点
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.size++;
  }

  //给定位置(索引)插入节点
  insert(value: T, position: number): boolean {
    if (position < 0 || position > this.size) {
      throw new Error("插入节点越界，请重新选择位置插入");
    }

    if (position === 0) {
      //头部插入
      this.prepend(value);
    } else if (position === this.size) {
      //从后面插入
      this.append(value);
    } else {
      //从中间插入
      const newNode = new DoublyNode(value);
      const current = this.getNode(position) as DoublyNode<T>;
      current.prev!.next = newNode;
      newNode.next = current;
      newNode.prev = current.prev;
      current.prev = newNode;
      this.size++;
    }
    return true;
  }

  //反向遍历
  postTraverse() {
    const arr: T[] = [];
    let current = this.tail;
    while (current) {
      arr.push(current.value);
      current = current.prev;
    }

    console.log(arr.join(" --> "));
  }

  //删除

  removeAt(position: number): T | null {
    if (position < 0 || position >= this.size) {
      throw new Error("删除越界，请重新传入要删除的索引值or位置");
    }

    let current = this.head;
    if (position === 0) {
      if (this.size === 1) {
        this.tail = null;
        this.tail = null;
      } else {
        this.head = this.head!.next;
        this.head!.prev = null;
      }
    } else if (position === this.length - 1) {
      this.tail = this.tail!.prev;
      this.tail!.next = null;
    } else {
      current = this.getNode(position) as DoublyNode<T>;
      current.next!.prev = current.prev;
      current.prev!.next = current.next;
    }

    this.size--;

    return current?.value || null;
  }
}

const dblList = new DoublyLinkedList();
dblList.append(1);
dblList.append(2);
dblList.append(3);

dblList.traverse();

dblList.prepend(0);
dblList.prepend(-1);
dblList.prepend(-2);

dblList.traverse();

dblList.insert("aaa", 0);
dblList.insert("bbb", 2);
dblList.insert("ddd", 8);
dblList.traverse();
// dblList.postTraverse();

dblList.removeAt(0);
dblList.removeAt(7);

dblList.traverse();

console.log(dblList.length, "长度");

export {};
